package com.ywk.base.dataStructure.algorithm;
//汉诺塔问题求解（分治算法）
public class HanoiTowerDemo {
//将全部盘分为两部分，最大的一个盘为一部分，上面的全部盘分为另一部分
	public static void main(String[] args) {
		hanoiTower(3, 'A', 'B', 'C');
	}
	
	//中间位置的是操作盘，操作盘作用就是将需要移动的盘在操作盘中临时存放,从最终目的来看b盘是操作盘，所以中间位置是b
	public static void hanoiTower(int nums,char a,char b,char c) {
		if(nums==1) {
			System.out.println("第1个盘从"+a+"->"+c);
		}else {
			//除最大的盘以外，将其他所有的盘从a移动到b（此时操作盘是c盘，所以中间位置是c）
			hanoiTower(nums-1, a, c, b);
			//将a中（剩下的）最大的盘移动到c
			System.out.println("第"+nums+"个盘从"+a+"->"+c);
			//将b中剩下的盘移动到c（此时操作盘是a盘,所以中间位置是a）
			hanoiTower(nums-1, b, a, c);
		}
	}
}
